package com.example.demo.leetcode.top100;

import java.util.LinkedList;
import java.util.List;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _49二叉树的最近公共祖先
 * @description
 * @date 2023/06/18 9:57
 * <p>
 * ******************************************************
 */
public class _49二叉树的最近公共祖先 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) return right;
        if (right == null) return left;
        return root;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
